1. Field
The present application relates generally to the operation of data networks, and more particularly, to methods and apparatus for encoding data in a communication network.
2. Background
In typical wireless delivery systems, content is delivered to portable devices over a multicast transmission channel. The content is in the form of code packets that are coded to overcome packet losses that may occur as packets are transmitted over the transmission channel. An encoder at a transmitter takes the original data packets and produces code packets that are transmitted to one or more devices. Because of noise or other degrading transmission effects, a subset of the code packets is received at any particular device. The received code packets are decoded to recover the original data packets.
Typically, a distribution server has an encoder that performs message coding on the data packets. The encoder takes the data packets (d) and produces code packets (C). The code packets are sent over the lossy transmission channel and some subset (C′) of the code packets (C) is received by a device. A decoder at the device uses the received code packets (C′) to recover the original data packets d.
The goal of message coding is to efficiently and reliably deliver content to a large number of mobile devices over a multicast wireless network. However, mobile devices are generally limited in their CPU capacity, amount of available memory, battery capacity, and the speed of their file systems. These constraints impose severe restrictions on the type of coding suitable for use in such an environment.
Typical coding schemes used to overcome packet erasures include Reed-Solomon codes and Raptor codes. Reed-Solomon codes are optimal codes in the sense that to recover k data packets, the decoder needs to receive exactly k code packets. However, the computational requirement for the decoding operation may be very high. In addition, the decoder memory requirements are also very high making it very difficult to implement on a mobile device.
Raptor codes are designed to overcome packet erasures in a network. The code consists of an inner LT-code designed to recover more than 99% of the data packets and an outer code designed to recover the rest. The computational capacity required for a Raptor decoder is far less than Reed-Solomon decoder. However, the Raptor codes are not as efficient as Reed-Solomon codes in terms of the number of code packets needed to recover all the data packets. For example, a Raptor decoder needs to receive about 1.1*k code packets to recover the k data packets with high probability.
Raptor codes are rateless codes. That is, the encoder can generate a large (potentially infinite) number of code packets, and as long as about 1.1*k code packets are received; the decoder can recover all the data packets. However, in most systems, it will not be necessary (or possible) to generate an infinite number of code packets. For example, typical distribution systems have a delivery deadline for a clip, and the distribution server has to stop transmitting code packets associated with the clip after its deadline has passed.
Another problem associated with Raptor coding is that it is a serial concatenation of codes. First an inner-code has to be decoded. These decoded packets are then fed to the outer decoder. These two steps have to be performed in sequence and this takes time to perform. Another problem with Raptor coding is that it takes more memory to perform the decoding operation than is typically available on a mobile device.
Therefore, it would be desirable to have a system that operates to provide a coding scheme that has low computational, memory, and overhead requirements for use in wireless environments.